#include <stdio.h>
#include "genlib.h"
#include "simpio.h"
#include "exception.h"
#include "helpers.h"
#include "knapsack.h"

typedef struct itemT{
	int num;
	int value;
	int weight;
}itemT;

void printItems(itemT *list, int numItems, int capacity);
int **newKP(int x, int y);

void knapsack(void)
{
	int numItems, capacity, i, j, w, I, W;
	int **matrix; 
	itemT *list;
	char c;
	string file;
	FILE *infile;


	file = getFilename();
	infile = fopen(file, "r");
	if(infile == NULL){
		Error("Could not find file.");
	}

	fscanf(infile, "%d", &numItems);
	list = NewArray(numItems+1, itemT);

	for(i=1; i<=numItems; i++){
		fscanf(infile, "%5d %5d %5d\n", &list[i].num, &list[i].value, &list[i].weight);
	}

	fscanf(infile, "%d", &capacity);

	printItems(list, numItems, capacity);

	matrix = newKP(numItems+1, capacity+1);

	for(w=0; w<=capacity; w++){
		matrix[0][w] = 0;
	}

	for(i=0; i<=numItems; i++){
		matrix[i][0] = 0;
	}

	for(i=1; i<=numItems; i++){
		for(w=0; w<=capacity; w++){
			if(list[i].weight <= w){
				if(list[i].value + matrix[i-1][w-list[i].weight] > matrix[i-1][w]){
					matrix[i][w] = list[i].value + matrix[i-1][w-list[i].weight];
				} else {
					matrix[i][w] = matrix[i-1][w];
				}
			}else{
				matrix[i][w] = matrix[i-1][w];
			}
		}
	}

	// Output:

	printf("\n\nKP solution:\n\n");

	if(capacity < 15){
		printf("  ");
		for(i=0; i<=capacity; i++){
			printf("%5d", i);
		}
		printf("\n\n");

		for(i=0; i<=numItems; i++){
			printf("%2d", i);
			for(j=0; j<=capacity; j++){
				printf("%5d", matrix[i][j]);
			}
			printf("\n");
		}
	}

	printf("\nOptimum value is: %d\n", matrix[numItems][capacity]);

	printf("Choose points to see what items are part of solution ( i,w ):\n");
	printf("?");
	while(TRUE){
		scanf("%d,%d", &I, &W);
		if((I>=0 && I<=numItems) && (W>= 0 && W<=capacity)) break;
		printf("Invalid input, please try again.\n");
	}

	printf("Items included: ");

	if(W > 0 && I > 0){
		while(I > 0 && W > 0){
			if(matrix[I][W] == matrix[I-1][W]){
				I--;
			}else{
				printf("%d ", I);
				if(W>0){
					W = W-list[I].weight;
					I--;
				}
			}
		}
	}else printf("none");
	printf("\nPress enter to continue.\n");
	scanf("%c%c", &c, &c);
}


void printItems(itemT *list, int numItems, int capacity)
{
	int i;
	printf("%d\n", numItems);
	for(i=1; i<=numItems; i++){
		printf("%5d %5d %5d\n", list[i].num, list[i].value, list[i].weight);
	}
	printf("%d\n", capacity);
}

int **newKP(int x, int y){
	int i, j, **newKP = NewArray(x, int *);

	for(i = 0; i < x; i++){
		newKP[i] = NewArray(y, int);
	}

	for(i=0; i<x; i++){
		for(j=0; j<y; j++){
			newKP[i][j] = 0;
		}       
	}

	return newKP;
}